In the United States, a standard has been proposed for digitally encoding high definition television signals. This standard is essentially the same as the MPEG2 standard, pro posed by the Moving Picture Experts Group (MPEG) of the Inter national Standards Organization (ISO). This standard is referred to herein as the MPEG standard and signal conforming to this standard are referred to as MPEG or MPEG encoded signals. This standard is described in a draft internal standard (DIS) publication entitled "Information Technology--Generic Coding of Moving Pictures and Associated Audio, Recommendation H.262 ISO/IEC 13818.2; 1995 (E) available from the ISO and incorporated by reference.
The MPEG2 video signal encoding standard specifies encoding video data representing an image into binary (digital) data consisting mostly of blocks of discrete cosine transfer (DCT) coefficients. These coefficients are run length encoded into fixed size run length codewords. Each run length encoded codeword is then Huffman encoded into variable length code words. In an MPEG encoded HDTV signal, blocks of DCT coefficients must be decoded at a predetermined rate in order to properly decode and display the image being transmitted. The instantaneous rate can vary depending upon the detail and motion in the image. However, there is a maximum rate at which run length encoded codewords, and thus variable length code words, occur for a `worst case` image. This rate exceeds 100 million code words per second. Various methods have been proposed to decode codewords at this rate.
Variable length decoders (VLDs) have been proposed in which have the capability of decoding multiple variable length codewords simultaneously in a single clock cycle, under the proper conditions. In prior art VLDs, a number of bits of the received encoded signal are supplied in parallel to the decoding section of the VLD via a barrel shifter. Such a VLD is termed a parallel decoder. The number of bits is selected to be at least the number of bits in the maximum sized variable length codeword. These bits are supplied to a lookup table (LUT), preconfigured with entries for each allowed variable length codeword. Each entry in the LUT contains the value of the run length codeword represented by the variable length codeword, and the length (i.e. the number of bits) of the variable length codeword. As a codeword is decoded, the number of parallel bits in the newly decoded variable length codeword are shifted out of the barrel shifter, and the remaining bits in the barrel shifter are shifted into their place. If necessary, the next bits in the digital bit stream are inserted into the barrel shifter. Then the remaining bits in the barrel shifter are processed to decode the next codeword. Such a VLD can decode a single variable length codeword in a single clock cycle.
However, as described above, for MPEG encoded HDTV signals, the maximum rate at which variable length codewords must be decoded is over 100 million per second. This requires a clock frequency of over 100 MHz. Operating at this frequency is currently beyond the capability of the integrated circuitry which is practical for consumer electronics. Thus, a VLD has been proposed which can decode more than one codeword per clock cycle. This would allow a VLD to be implemented which can operate with a clock signal rate below the 100 MHz rate which would be required in the circuitry described above.
In U.S. Pat. No. 5,225,832, entitled "High Speed Variable Length Decoder", issued Jul. 6, 1993 to Wang et al., a parallel VLD is disclosed. In Wang et al., it is recognized that because the variable length codewords vary in length, it is possible that more than a single variable length codeword may fit within the number of bits in the maximum sized variable length codeword. The decoding LUT includes further entries for combined short codewords. Thus, should two shorter codewords be present simultaneously at the output of the barrel shifter, the two codewords will be recognized by the LUT and decoded simultaneously. This allows the VLD to decode at a rate higher than one codeword per clock cycle. The increase over the single-codeword-per-clock-cycle is further increased because shorter codewords are statistically more likely to occur than longer ones. This increase of decoding rate comes at the expense of increased complexity of the decoding LUTs.
It has also been suggested that the width of the output from the barrel shifter be increased to produce two maximum sized variable length codewords simultaneously. This doubled width barrel shifter output is supplied to an LUT which will recognize two codewords simultaneously. A first portion of the LUT recognizes the first variable length codeword, and a second portion recognizes the second variable length codeword. The LUT produces three output values: a first value represents the first variable length codeword, a second value represents the second variable length codeword, and a third value represents the length of the combined two codewords. Such an arrangement would enable the VLD to operate at a clock rate of around 50 MHz, which is well within the practical range. However, the LUT in such an arrangement is very large, compared to that in the single variable length codeword per clock cycle arrangement. For each codeword entry in the first portion of the LUT, the LUT must include circuitry for looking up the complete set of codewords for the second portion. If there are n allowable codewords, there must be n squared entries. This makes the LUT large and slow in operation.
In an article, "Pair-Match Huffman Transcoding to Achieve a Highly Parallel Variable Length Decoder with Two-Word Bit Stream Segmentation" by Bakhmutsky, published in the SPIE Proceedings, Volume 3021, pages 247-265, an enhancement to the parallel VLD of the type disclosed in Wang et al. is disclosed. The VLD of Bakhmutsky can decode at least two DCT coefficients per clock cycle. Bakhmutsky recognizes that the output of the VLD is a series of fixed length run length encoded codewords, each corresponding to a received variable length codeword. Each run length codeword represents one or more DCT coefficients, and includes a run portion and a value portion. The run portion represents the number of zero valued DCT coefficients before the coefficient represented by the current code word. The value portion represents the value of the non-zero DCT coefficient following the run of zero valued coefficients.
Bakhmutsky recognized that a zero run run-length codeword, represented by a single variable length codeword, represents only a single coefficient value (i.e. zero zero-valued coefficients), and that a one run run-length codeword, represented by a single variable length codeword, represents two coefficients: one zero-valued coefficient, and one non-zero valued coefficient. Should two variable length codewords representing two respective zero run run-length codewords, each representing a single coefficient, occur sequentially, they must be decoded simultaneously in a single clock cycle in order to maintain the two coefficient per clock cycle decoding rate. Furthermore, a variable length codeword representing a zero run run-length code (i.e. one coefficient) followed by a variable length codeword representing a one run run-length codeword (i.e. two coefficients) must also be decoded simultaneously in a single clock cycle in order to maintain the two coefficient per clock cycle decoding rate. If this were not done, that is, if each were separately decoded in one clock cycle, then three coefficients would be decoded in two clock cycles (i.e. 1.5 coefficients per clock cycle), which would drop below the goal of two coefficients per clock cycle. In all other cases, a single variable length codeword can be decoded in a single clock cycle and still maintain the goal of at least two coefficients per clock cycle.
In the MPEG encoding scheme, any run-length codeword may be represented by a variable length codeword having a size of up to 24 bits wide (e.g. an escape sequence). This is the maximum size that an MPEG variable length codeword can be. Thus, two sequential variable length codewords can, potentially, be 48 bits wide. Bakhmutsky proposed to analyze the input signal to the VLD, and to replace the variable length codewords representing zero run and one run run-length codes with respectively different codewords having fewer bits in such a manner that two sequential transcoded codewords can appear simultaneously at the output of the VLD barrel shifter. The LUT is modified to recognize the transcoded codewords and decode them simultaneously. In this manner, the Bakhmutsky system can recognize and decode two variable length codewords representing two sequential zero run run-length codewords, or a zero run run-length codeword followed by a one run run-length codeword in a single clock cycle, and thus maintain a two coefficient per clock cycle decoding rate.
The Bakhmutsky system, however, requires the addition of a transcoder in the signal path before the VLD, and the modification of the VLD LUTs to recognize and process two sequential transcoded codewords simultaneously. A system which can maintain a decoding rate of at least two coefficients per VLD clock cycle, without requiring additional decoding or transcoding circuits, and without requiring look up tables in which n squared entries are required for n variable length codewords is desirable.